package task1;



public class test {
    public static void main(String[] args) {
        int[] array=new int[100000000];
        for(int i=0;i<array.length;i++)
        {
            array[i]=(int)(Math.random()*array.length);
        }
        long start=System.currentTimeMillis();
        quickSort(array,0,array.length-1);
        System.out.println(System.currentTimeMillis()-start);
    }

    private static void quickSort(int[] array, int left, int right) {
        if(left>right) return;

        int q=partition(array,left,right);

        quickSort(array,left,q-1);
        quickSort(array,q+1,right);

    }

    private static int partition(int[] array, int left, int right) {
        int sortIndex=left;//分治元素的下标
        int arrayIndex=left;//数组下标
        int pivot=array[right];//对照元素

        while (arrayIndex<right)
        {
            if(array[arrayIndex]<pivot)//如果当前元素比对照元素小，则将其与分治元素交换
            {
                int temp=array[arrayIndex];
                array[arrayIndex]=array[sortIndex];
                array[sortIndex]=temp;
                sortIndex++;
            }
            arrayIndex++;
        }
        array[right]=array[sortIndex];//最后将对照元素与分治元素交换位置
        array[sortIndex]=pivot;
        return sortIndex;
    }
    private static void maopao(int[] array)
    {
        for(int i=0;i<array.length;i++)
        {
            for(int j=i+1;j<array.length-1;j++)
            {
                if(array[j]<array[j+1])
                {
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
        }
    }

}
